package com.boot.test;

/**
 * 链表
 *
 * @param <T>
 */
public class NodeDemo<T> {

    class Node {
        private T data;
        private Node next;

        public Node(T data, Node next) {
            this.data = data;
            this.next = next;
        }
    }


    //头节点
    private Node head;
    //尾节点
    private Node tail;
    int size;


    /**
     * 每次在尾部插入
     *
     * @param element
     */
    public void addTailNode(T element) {
        if (head == null) {
            head = new Node(element, null);
            tail = head;
        } else {
            Node node = new Node(element, null);
            tail.next = node;
            tail = node;
        }
        size++;
    }

    /**
     * 在链表头部插入
     *
     * @param element
     */
    public void addHeadNode(T element) {
        head = new Node(element, head);
        if (tail == null) {
            tail = null;
        }
    }

    /**
     * 在指定位置插入新节点
     *
     * @param element
     */
    public void addIndexNode(T element, int index) {
        if (head == null || index == 0) {
            addHeadNode(element);
        } else {
            Node pre = findNodeByIndex(index);
            Node node = new Node(element, pre);
            //插入后pre的next指向新节点，新节点的next指向原来pre的下一个节点
            pre.next = node;
            size++;
        }

    }

    /**
     * 根据索引查询到节点
     *
     * @param index
     */
    public Node findNodeByIndex(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("链表越界");
        }
        Node current = head;
        int t = 0;
        while (current != null) {
            if (t == index) {
                break;
            }
            current = current.next;
            t++;
        }
        return current;
    }
    /**
     * 根据节点查询节点存放的位置
     * @param element
     * @return
     */
    public int findIndexByNode(T element) {
        Node current = head;
        int index = 0;
        while (current != null) {
            if (current.data.equals(element)) {
                return index;
            }
            current = current.next;
            index++;
        }
        return -1;
    }

    public boolean isEmpty() {
        return size == 0 ? true : false;
    }

    /**
     * 清空链表
     */
    public void clear() {
        head = tail = null;
        size = 0;
    }

    /**
     * 根据节点位置删除指定位置的节点
     * @param index
     * @return
     */
    public T deleteNode(int index) {
        Node dNode = null;
        if(index < 0 || index > size-1)  {
            throw new IndexOutOfBoundsException("链表越界");
        }
        if (index == 0) {
            dNode = head;
            head = head.next;
        }else {
            Node pre = findNodeByIndex(index-1);//获取要删除的节点的前一个节点
            dNode = pre.next;//要删除的节点就是pre的next指向的节点
            pre.next = dNode.next;//删除以后pre的next指向被删除节点之前所指向的next
            dNode.next = null;
        }
        return dNode.data;
    }
    /**
     * 打印链表
     */
    public String toString() {
        Node node = head;
        StringBuffer sb = new StringBuffer();
        while (node != null) {
            sb.append(node.data+" ");
            node = node.next;
        }
        return sb.toString();
    }




    public static void main(String[] args) {
        NodeDemo<String> nodeDemo = new NodeDemo<String>();
        nodeDemo.addTailNode("111");
        nodeDemo.addTailNode("222");
        nodeDemo.addTailNode("333");
        nodeDemo.addTailNode("444");
        System.out.println(nodeDemo);
        System.out.println("链表的size:" + nodeDemo.size);
        System.out.println("删除某个节点的位置:" + nodeDemo.findIndexByNode("333"));
        System.out.println("查询指定位置的节点:" + nodeDemo.findNodeByIndex(2).data);
        System.out.println("删除指定位置的节点:" + nodeDemo.deleteNode(2));
        System.out.println(nodeDemo);
        System.out.println("链表是否为空:" + nodeDemo.isEmpty());
        nodeDemo.clear();
        System.out.println("清空后的链表:" + nodeDemo);
        System.out.println("链表是否为空:" + nodeDemo.isEmpty());
    }

}
